%!TEX root = ../main.tex

% 约20页
\chapter{研究现状与预备知识}
% 原则上，每一章开头不可马上进入第一节
% 需要一段引文提要起到 TL;DR 的作用
\section{硬件性能监控计数器与多路复用}

\subsection{硬件性能监控计数器}

在计算机体系结构性能分析领域，硬件性能监控计数器(Performance Monitoring Counters, PMCs) 是关键的分析工具，用于测量关键性能事件，如时钟周期、缓存缺失、分支预测失败、内存指令退休等。这些事件的计数可以用于计算重要的性能指标，如CPI(每条指令周期数)、MPKI(每千条指令缓存未命中数)和分支预测错误率。

% 增加图说明指标和硬件事件之间的关系

PMCs主要分为两类：
% TODO 统一表述 缩写只写一次
\begin{itemize}
    \item \textbf{固定计数器（Fixed PMCs）}：专用于特定高频事件（如时钟周期、退役指令数），不可重配置。主流平台（如x86-64、Arm）通常配置1-4个固定计数器。
    \item \textbf{通用计数器（Generic PMCs）}：可通过事件选择寄存器编程监测任意支持的事件。通常配置4-8个通用计数器，但可监测的事件类型可达数百种。
\end{itemize}


% 表格：补充介绍各个平台上的PMC数量


在现代处理器性能分析场景中，硬件性能监控单元（Performance Monitoring Unit, PMU）所提供的硬件性能监控计数器（PMC）数量通常有限（如 x86-64 处理器通用计数器多为 4-8 个），但现代的微架构分析方法学如自顶向下微架构分析方法（Top-down Microarchitecture Analysis, TMA）\cite{DBLP:conf/ispass/Yasin14_top_down}需监控的微架构事件却多达上百种，这种有限计数器资源与海量事件需求之间的矛盾推动了两类主流解决方案的发展：轨迹对齐（Trace Alignment） 与多路复用（Multiplexing） 。

% 增加表格说明各个平台上的Fixed Counters 、 Generic Counters 观测的硬件事件


\subsection{轨迹对齐} 

轨迹对齐（Trace Alignment）的核心思路在于通过多轮独立的程序执行与性能采样，实现对全部目标事件的无估算误差覆盖。具体而言，在每一轮执行中，该方法利用有限的PMC资源仅监控部分硬件事件子集，确保该子集内的事件在整个执行周期内被持续计数。这一设计从根本上规避了传统硬件事件复用技术中因时间分片导致的未监控阶段事件计数插值估算误差；随后，通过时间轴对齐或上下文匹配算法，将多轮执行产生的离散性能轨迹，包含事件计数与时间/任务上下文的数据集，融合为一份完整、连贯的全局执行剖面（Global Execution Profile），从而实现对程序硬件行为的全面刻画。

轨迹对齐技术的核心优势在于其数据精度的可靠性，这种可靠性源于每轮执行中事件的持续监控特性，无需依赖统计假设进行计数推断。因此，该技术天然适用于执行特性稳定、输入确定性强的可复现工作负载，例如基准测试套件、科学计算程序等。这类工作负载的执行流程与硬件交互模式具有高度一致性，多轮执行间的行为变异极小，为轨迹对齐的时间轴或上下文匹配提供了稳定的基础，确保融合后的剖面能真实反映程序的硬件性能特征。

早期针对轨迹对齐的研究主要聚焦于单线程程序场景，核心挑战在于解决多轮执行中性能数据的时间轴一致性问题——即如何消除因测量启动/结束时机差异、系统微小扰动（如时钟漂移）导致的时间偏移，实现离散轨迹的精准映射。Hauswirth等人\cite{DBLP:conf/oopsla/HauswirthDSM05}首次系统性地提出了面向性能指标时间序列的轨迹对齐方案，其核心技术是动态时间规整（Dynamic Time Warping, DTW）算法。该算法通过分析不同测量轮次中“锚定事件”（如指令退休事件、全局时钟周期事件）的时间戳关联性，构建多轮轨迹间的非线性时间映射关系，从而将离散的硬件事件计数（如缓存访问、分支预测失败）统一到同一时间参考框架下。例如，在监控单线程程序的L1数据缓存缺失时，该方法可通过指令退休事件的同步性，将不同轮次测量的缓存缺失计数精准关联到程序的指令执行序列中，避免了时间偏移导致的计数错位，为单线程程序的多轮性能轨迹融合提供了有效解决方案。

随着并行计算技术的普及，多线程与任务并行程序（如基于OpenStream、OpenMP的并行应用）的性能分析需求日益增长，传统单线程轨迹对齐方法的局限性逐渐凸显。并行程序的动态性——包括任务的动态调度、线程间的依赖关系（如数据依赖、控制依赖）、共享硬件资源（如L3缓存、内存总线）的竞争——导致多轮执行间的线程行为与事件上下文易发生混淆，传统时间轴对齐难以区分不同线程或任务的事件归属，进而引发融合数据的失真。针对这一问题，Neill等人\cite{neill_fuse_nodate}提出的Fuse方法对轨迹对齐技术进行了关键性扩展，将对齐维度从“时间轴”进一步延伸至“任务上下文”，通过构建“任务创建图（Task Creation Graph, TCG）”解析并行程序的任务生命周期与依赖结构，实现了并行场景下线程级与任务级数据的精准匹配。

尽管轨迹对齐技术在离线性能分析中展现出优异的精度，但其固有局限性仍限制了其应用场景的拓展。首先，多轮执行带来的时间开销呈线性增长——若目标事件数量为 $M$，每轮执行可监控的事件数为 $K$（由 PMC 数量决定），则所需执行轮次至少为 $\lceil M/K \rceil$，当 $M$ 达到数十个（如 PAPI 支持的 33 个硬件事件）时，执行轮次可能增至十余次，导致总分析时间大幅延长，难以满足实时性能监控的需求。其次，该技术对工作负载的“可复现性”具有严苛要求：其依赖多轮执行间的行为一致性（如任务创建顺序、硬件资源访问模式），而在云服务、微服务等动态场景中，工作负载特性随用户请求动态变化，性能劣化或瞬态故障（如毫秒级的缓存颠簸）可能仅出现于单次执行中，多轮执行不仅无法及时捕捉此类瞬态事件，还可能因负载波动导致多轮数据的上下文不可比（如动态频率缩放、缓存纠错机制引发的执行时间变异）。此外，Fuse\cite{neill_fuse_nodate} 等方法虽通过任务创建图与行为聚类提升了并行场景的适应性，但仍无法完全应对非确定性并行程序（如含随机任务调度的应用）的行为变异，进一步限制了其适用范围。

% 综上，轨迹对齐技术目前更多应用于离线性能分析领域，例如基准测试程序的性能优化如面向SPEC CPU套件的编译器调优、科学计算程序的硬件瓶颈定位等场景，这些场景允许较长的分析周期且工作负载可复现；而在在线故障诊断、动态负载的实时性能监控等领域，该技术仍面临难以逾越的时间开销与可复现性障碍。


\subsection{多路复用}

多路复用是实现有限PMCs监测大量微架构事件的核心技术，其工作流程由两个紧密耦合的核心环节组成：硬件事件调度与硬件性能计数器缩放。这两个环节协同工作，共同解决"事件规模庞大-计数器资源有限"的矛盾。

硬件事件调度环节负责在时间维度上合理分配有限的PMCs资源，其核心在于通过轮询（Round-Robin）或优先级调度策略，让不同事件在不同时间片内轮流占用PMCs资源。调度策略的设计直接影响监测精度与系统开销，如时间片的长度选择需在响应速度与切换开销间取得平衡；同时，调度策略也决定了各事件的监测时机与时长，为后续的缩放计算提供必要参数。

硬件性能计数器缩放环节则是在事件调度的基础上，通过数学方法估算事件的真实发生次数。由于每个事件仅在部分时间片内被监测，其原始计数无法直接反映实际行为。因此，需要基于"采样比例"——即事件被调度执行的时间与总测量时间的比值，对原始计数值进行线性缩放，从而估算完整测量周期内事件的真实计数。缩放算法的精度直接决定了多路复用技术的可靠性，后续将详细探讨各类优化缩放算法的设计与实现。

这两个环节紧密配合：调度策略决定了事件的监测时机与时长，为缩放算法提供必要的采样比例参数；而缩放算法则通过数学方法补偿调度过程中的信息缺失，还原事件的真实行为。在后续章节中，我们将分别深入探讨硬件事件调度调度方法的研究现状与性能数据缩放算法的优化策略，分析不同技术的优缺点及其适用场景。

硬件性能计数器缩放环节则是在事件调度的基础上，通过数学方法估算事件的真实发生次数。由于每个事件仅在部分时间片内被监测，其原始计数无法直接反映实际行为。因此，需要基于"采样比例"，即事件被调度执行的时间与总测量时间的比值，对原始计数值进行线性缩放，从而估算完整测量周期内事件的真实计数。缩放算法的精度直接决定了多路复用技术的可靠性，后续将详细探讨各类优化缩放算法的设计与实现。

这两个环节紧密配合：调度策略决定了事件的监测时机与时长，为缩放算法提供必要的采样比例参数；而缩放算法则通过数学方法补偿调度过程中的信息缺失，还原事件的真实行为。在后续章节中，我们将分别深入探讨硬件事件调度调度方法的研究现状与性能数据缩放算法的优化策略，分析不同技术的优缺点及其适用场景。

该方法无需多轮测量，可实时覆盖多事件，成为 Linux \texttt{perf}~\cite{linux_perf_source}, LIKWID~\cite{treibig_likwid_2010}, ARM Top-down Tool~\cite{arm_topdown_tool}, Intel Emon 等主流工具的核心技术，尤其适用于动态、不可复现的场景（如云函数、实时数据处理）。


\section{硬件事件调度方法研究现状}

\subsection{传统硬件事件调度方法：静态调度与基础复用}
早期PMCs复用技术的事件调度以静态策略为核心，其设计初衷是通过预定义的固定规则分配监测资源，降低实现复杂度与运行时开销，满足离线性能分析等场景的基础需求。这类方法虽易于部署，但未能考虑事件的动态特性与硬件平台差异，导致监测精度和资源利用率存在明显瓶颈，难以适配复杂多变的应用场景。

\subsubsection{轮询式复用（Round-Robin Multiplexing）}
轮询式复用是当前主流性能分析工具如Linux perf\_event子系统、PAPI（The Performance Application Programming Interface）默认采用的基础事件调度策略，其核心逻辑是将待监测事件划分为若干组，在固定时间片（如Linux perf\_event默认4ms，与CPU调度周期对齐）内让各组事件轮流占用PMCs资源；对于每组内的事件，若数量不超过当前核心可用PMCs数量，则通过硬件并行监测；若超出则进一步拆分至后续分组。由于事件仅在部分时间片内被监测，其最终计数需通过线性插值估算——即根据事件实际监测时长占总分析时长的比例，对原始监测计数进行缩放。

该方法的优势在于实现逻辑简单、运行时开销低，无需复杂的事件特性分析与动态调整，可快速集成至各类系统工具中。但在实际应用中，其局限性逐渐凸显：首先，时间片均分策略未考虑事件的动态速率差异，对于程序负载表征变化导致速率波动大的事件，长时间未监测会导致线性插值误差剧增，部分场景下误差可达30\%以上；其次，同一性能指标所需的关联事件被分散在不同时间片监测，导致计算出的指标值与实际行为存在显著偏差，尤其在程序执行阶段频繁切换的场景下，可靠性问题更为突出；再次，未区分固定PMCs与通用PMCs的硬件功能差异——固定PMCs仅能监测特定事件，通用PMCs可配置监测任意事件，但轮询式复用常将两类事件混排调度，导致固定PMCs空闲时通用事件无法利用其资源，部分平台下PMCs利用率下降37.5\%。

\subsubsection{预定义事件分组（Predefined Event Grouping）}
为解决轮询式复用中"同一性能指标关联事件不同步监测"导致的指标可靠性问题，研究人员提出了预定义事件分组策略，典型代表为LIKWID（Lightweight Performance-Oriented Tool Suite）与ARM Top-down Tool。其核心设计思想是：根据性能指标的计算需求，将关联事件划分为固定分组，确保组内事件在同一时间片内并行监测，避免因事件监测时段错位导致的指标计算偏差；分组大小根据主流处理器的PMCs数量预定义（如LIKWID的L2CACHE组含2个事件，BRANCH组含2个事件），确保组内事件数量不超过常见平台的PMCs容量，无需拆分。

该方法通过保证指标关联事件的同步性，显著提升了性能分析的可靠性，例如LIKWID的预定义分组可准确计算Cache MPKI（Misses Per Kilo Instructions）、CPI（Cycles Per Instruction）等关键指标，为离线性能优化提供可信数据。但该策略仍存在明显局限：一是分组大小固定，无法适配不同平台的PMCs数量差异——在配备8个通用PMCs的高端处理器上，若预定义分组仅含2个事件，则6个PMCs处于空闲状态，资源利用率仅为25\%；二是组间调度仍采用轮询式均分时间片，未根据事件的重要性与监测需求优化调度顺序与时长，导致低优先级组的采样率过低（如ARM Top-down Tool在处理14个事件组时，平均采样率仅为21.42\%）；三是跨平台适配成本高，不同处理器的事件约束规则存在差异，若预定义分组中包含某平台的冲突事件，需手动调整分组结构，难以实现自动化部署。

\subsection{动态事件调度方法：基于不确定性建模与弹性调度的优化}
随着云计算、边缘计算等场景的发展，在线性能分析如云资源动态调度、实时故障诊断等需求日益增长，传统静态方法的精度不足、适应性差等问题日益突出。在此背景下，动态事件调度方法应运而生，其核心思路是通过实时分析事件的动态特性（如速率波动、监测误差），动态调整事件的PMCs分配方案与调度时长，以最小化监测误差并提升资源利用率。其中，TinTin作为该方向的代表性工作，构建了一套基于事件不确定性建模与弹性实时调度的完整框架，显著提升了PMCs复用的动态适配能力。

\subsubsection{事件不确定性建模与量化}

TinTin首先明确PMCs复用误差的本质来源：事件在未被监测时段内的真实速率无法直接获取，导致计数估算存在不确定性。为此，该框架提出以方差为代理指标的不确定性量化方法，通过实时分析事件的监测数据推导不确定性大小。具体而言，TinTin将事件的瞬时速率视为随机变量，在每个监测时段内，根据事件的计数（$x_j$）与监测时长（$\delta_j$）计算平均速率（$r_j = x_j/\delta_j$），并采用Welford增量算法实时更新速率方差（$V(r_i)$）——该算法无需存储历史数据，可有效降低运行时开销；对于未监测时长（$t$）内的计数误差，通过速率方差推导得出，即计数方差为$V(x_i,t) = V(r_i) \cdot t^2$，事件的不确定性则定义为该方差的平方根（$\sigma_i = \sqrt{V(x_i,t)}$）。

这种建模方式的优势在于无需离线校准或特殊硬件支持，可实时反映事件的动态波动特性，如程序性能表征变化导致的速率突变等，为后续调度优化提供量化依据。例如，在SPEC 2017的541.leela\_r基准测试中，TinTin监测发现"L1-dcache-load-misses"事件的速率方差是"bus-cycles"事件的3倍，因此为前者分配更多监测时间以降低不确定性，使该事件的计数误差降低42%。

\subsubsection{基于弹性调度的事件调度优化}
基于事件不确定性的量化结果，TinTin将事件调度问题转化为弹性实时调度问题，核心目标是在PMCs数量约束下，最小化所有事件的总不确定性。该框架以"事件占用PMCs的时长比例（即利用率$U_i$）"为优化变量，构建二次优化模型：
\begin{equation}
\min_{U_i} \sum_{i=1}^n \frac{w_i V(r_i)}{x_i^2} \cdot (1-U_i)^2
\end{equation}
\begin{equation}
\text{s.t. } \sum_{i=1}^n U_i \leq m, \quad U_{\text{min}} \leq U_i \leq 1
\end{equation}
其中，$w_i$为用户指定的事件权重，用于区分事件的监测优先级，$m$为当前核心的可用PMCs数量，$U_{\text{min}}$为最小利用率阈值（TinTin设为超周期的1/10，避免事件长期饥饿）。该模型的物理意义清晰：为速率方差大（不确定性高）、权重高的事件分配更高利用率，同时避免单一事件过度占用资源。

在多PMCs场景下，TinTin通过"超周期（Hyperperiod）"归一化调度周期（默认与CPU调度周期对齐为4ms），将多个PMCs视为"虚拟单资源"，按事件不确定性从高到低的顺序分配资源——若某事件的利用率超出当前PMCs的剩余容量，则将其拆分至下一个PMCs的空闲时段，确保无时间重叠。例如，在2个PMCs上调度3个事件时，事件1（$U_1=0.6$）被分配至PMCs 1的[0,0.6)时段，事件2（$U_2=0.5$）被拆分至PMCs 1的[0.6,1)与PMCs 2的[0,0.1)时段，事件3（$U_3=0.4$）被分配至PMCs 2的[0.1,0.5)时段。该调度方式的时间复杂度为$O(n \log n)$（主要来自事件按不确定性的排序），运行时开销可控制在2.4\%以内，满足在线监测需求。此外，TinTin通过"事件组扩展"机制支持关联事件的同步监测，进一步提升指标可靠性，在Pond云资源调度系统的实验中，其latency敏感性预测精度较轮询式复用提升64\%。

尽管TinTin显著优化了动态场景下的PMCs复用效果，但其在实际大规模部署中仍存在关键瓶颈：一是依赖ePX机制实现事件监测与调度，而该机制需通过LLVM插桩或对操作系统内核进行侵入式修改，大幅提高了在大规模数据中心场景的部署门槛，且运行时插桩会引入额外性能开销，部分高负载场景下系统吞吐量下降15\%以上；二是采用sched\_switch tracepoint监听CPU调度事件以同步调度周期，在高线程并发场景下该tracepoint成为性能热点，导致多核高负载时的调度可扩展性存疑；三是仅基于事件速率方差分配采样资源，而方差指标难以适配云计算微服务的剧烈波动场景——微服务的突发行为往往伴随短时间内的速率突变，方差计算需积累一定监测数据，导致TinTin对这类阶段性关键事件的响应滞后，突发时段的监测误差升高30\%-50\%。

\subsection{跨平台自适应事件调度方法：分组优化与资源利用率提升}
传统静态方法与动态方法的局限性促使研究人员提出跨平台自适应事件调度方法，旨在突破固定PMCs数量假设的约束，通过动态优化事件分组策略以适应不同硬件平台与运行环境。在这一领域，hperf工具的自适应分组策略是具有代表性的研究成果，其核心在于通过事件组合并与优化，在保证性能指标可靠性的前提下，最大化PMCs利用率与采样率，从而提升复用效率。

自适应事件分组策略的理论基础在于：将关联强劲的事件（即用于计算同一性能指标的事件）进行同步监测是确保指标可靠性的前提，但传统固定分组方法未充分考虑PMCs容量限制与事件组合的灵活性。基于这一认识，hperf提出两阶段分组优化方法：首先，根据性能指标计算需求划分原始事件组，确保关联事件同步监测以保障指标计算的准确性；其次，通过自适应合并策略优化组结构，即反复筛选事件数量较少的组进行合并，以充分利用可用PMCs资源。具体而言，该合并过程以组规模最小化为优化目标，优先选择能产生最小合并组的组合进行尝试，若合并后的组规模未超过平台可用PMCs数量，则执行合并操作。这种策略能够有效减少总事件组数，从而在轮询复用中提高每个事件组的实际监测时长比例，即提升采样率。

在实验验证中，hperf的自适应分组策略展现出显著的性能优势。与LIKWID等传统工具相比，其PMCs利用率从78.57\%提升至96.43\%，同时平均采样率从16.67\%提升至25\%。在ARM架构平台的适配测试中，该策略同样有效，使采样率从21.42\%提升至33.33\%，且无需针对不同架构手动调整分组结构，显著降低了跨平台应用的配置成本。然而，该方法仍存在三方面局限性：其一，贪心合并策略虽能快速获得可行解，但无法保证全局最优性，导致部分场景下PMCs资源未能被充分利用；其二，为适应贪心合并逻辑而压缩的观测窗口降低了事件速率的采样粒度，在微服务短事务等场景下，部分事件的速率估算精度受到影响；其三，事件分组的初始划分仍依赖人工配置，面对未知性能指标时缺乏自适应调整能力，限制了其在复杂动态场景中的应用灵活性。

\subsection{研究总结与现有挑战}
综上所述，PMCs复用中的硬件事件调度方法已从传统静态调度演进至动态优化与跨平台自适应阶段：传统静态方法（轮询式复用、预定义分组）以低开销、易部署为优势，适用于离线性能分析，但受限于固定规则，资源利用率与精度难以满足复杂场景需求；动态方法（以TinTin为代表）通过不确定性建模与弹性调度，提升了动态场景的精度与适应性，但存在部署门槛高、高并发可扩展性差、突发行为响应滞后等问题；跨平台自适应方法（以hperf为代表）通过可用PMCs检测与贪心合并，解决了平台适配问题，但贪心策略的次优性、观测窗口导致的精度损失、分组初始划分的手动依赖，仍制约其实际应用效果。

当前该领域仍面临三大核心挑战：一是部署开销与监测精度的平衡，现有动态方法多依赖侵入式修改或高频事件监听，难以在大规模数据中心场景实现低开销部署；二是复杂场景的自适应能力，如何在微服务突发行为、多核高并发等场景下，实现事件特性的实时感知与调度策略的快速调整，仍是关键难题；三是全自动化分组与优化，现有方法仍依赖人工定义事件与指标的关联关系，如何通过数据驱动方法自动识别关联事件、生成最优分组，是提升跨平台适配能力的核心方向。

\section*{性能数据缩放算法}

性能数据缩放算法是突破物理计数器数量限制、实现多类微架构事件同步监测的核心技术支柱，其发展脉络始终围绕“提升估算精度”与“适配动态场景”两大目标展开，且各阶段技术均需在工程实现复杂度与监测准确性之间寻求平衡。

线性缩放（Linear Scaling）是多路复用的基础估算方法，其核心公式如下。该公式通过将事件在部分时间内的原始计数值按照监测时间比例进行放大，估算出完整测量周期内的真实计数。公式中，$\hat{c}$表示估算的事件总计数，$c_{\text{raw}}$为硬件计数器记录的原始计数值，$t_{\text{enabled}}$代表事件实际被监测的时间，$t_{\text{total}}$为总测量时间。计算过程直观：首先计算事件的实际监测比例（$t_{\text{enabled}} / t_{\text{total}}$），然后用原始计数值除以该比例，即可得到放大后的估算总计数。

\begin{equation}
    \hat{c} = \frac{c_{\text{raw}}}{t_{\text{enabled}} / t_{\text{total}}}
\end{equation}

线性缩放方法最大的优势在于实现简单、计算开销小，且易于集成到各类性能分析工具中。正因如此，该方法被广泛应用于主流性能监测工具，如Linux perf\_event子系统和PAPI等。这些工具默认采用线性缩放作为多路复用的基础估算策略，为用户提供便捷的性能数据采集能力。

然而，Banerjee 等人\cite{banerjee_bayesperf_2021}通过实验证明，估算误差随采样比例降低而显著增大。特别地，当采样比例低于 50\% 时，相对误差可能超过 20\%。这一现象可形式化描述为：

\begin{equation}
    \left| \frac{\hat{c} - c_{\text{true}}}{c_{\text{true}}} \right| \propto \frac{1}{t_{\text{enabled}} / t_{\text{total}}}
\end{equation}
其中 $c_{\text{true}}$ 表示事件的真实发生次数。

这一发现表明，线性缩放对“事件发生频率在时间维度均匀分布”的强假设，在实际场景中难以成立——当应用存在突发指令流（如分支预测失败集中爆发）或数据局部性动态变化时，固定比例的缩放逻辑会显著偏离真实计数，成为误差的主要来源。

为克服线性缩放的固有缺陷，技术演进首先朝着“优化时间维度插值逻辑”方向推进，Mathur等人\cite{mathur_improved_2005}提出的时间插值法通过在调度间隔内插入中间采样点，利用相邻周期的计数变化趋势修正离散采样的误差，一定程度上缓解了均匀分布假设的局限性；Mytkowicz等人\cite{DBLP:conf/ipps/MytkowiczDHS06}则构建了估算精度评估框架，通过多轮测量的真实数据与多路复用估算数据的对比，量化不同方法的误差边界，为工具选型提供了量化依据。

% 为提升估算精度，Mathur等人提出时间插值法，在调度间隔内插入中间采样点，通过相邻周期的计数变化趋势修正离散采样的误差；Wang等人的NeoMPX方法引入非线性模型，针对事件计数的非均匀分布（如突发分支预测失败），动态调整缩放系数，而非依赖固定线性比例；Mytkowicz等人\cite{DBLP:conf/ipps/MytkowiczDHS06}则构建了估算精度评估框架，通过对比多轮测量的真实数据与多路复用的估算数据，量化不同方法的误差边界，为工具选择合适的估算策略提供依据。

而Wang等人提出的NeoMPX方法\cite{neill_fuse_nodate}，进一步突破了线性假设的束缚，引入非线性增长速率梯度估算模型（分为离散时间切片的DCAM与连续时间的CAM），针对事件计数的非均匀分布特征（如突发分支预测失败、缓存访问波动）动态调整缩放系数。相较于线性缩放的固定比例策略，NeoMPX通过指数形式的非线性插值（如DCAM中基于\(m = \sqrt[t+1]{\frac{count_{\text{recorded}}^{i+1}}{count_{\text{recorded}}^{i}}}\)计算增长梯度），更好地适配了事件发生的动态性，在16个硬件事件的同步监测场景中，相较于PAPI默认的线性缩放，精度提升最高达59\%。但NeoMPX的技术局限同样显著：其非线性模型依赖预设的固定计算策略（如指数增长假设），对实际场景中微架构事件的复杂动态特性拟合能力不足——例如，当应用负载在计算密集与访存密集阶段频繁切换时，预设的非线性梯度难以实时匹配事件发生模式的突变，导致部分场景下估算精度仍出现波动，未能完全摆脱“模型假设与实际场景脱节”的问题。


随着对微架构事件关联性认知的深化，Banerjee等人2021年提出的BayesPerf\cite{banerjee_bayesperf_2021}实现了技术范式的跃迁，将贝叶斯统计与概率因子图（Factor Graph）引入性能数据缩放，标志着算法设计从“单一事件拟合”转向“多事件关联推理”。该方法的核心创新在于：基于CPU厂商提供的微架构指标计算公式，提取事件间的固有关联（如LLC缺失数、DMA事务大小与DRAM带宽的代数关系），并将这些关系编码为因子图中的联合概率分布与条件概率依赖，通过期望传播（EP）算法实现多事件的联合推理，从而在缩放过程中利用关联事件的准确计数修正目标事件的估算误差。实验表明，在事件多路复用时，BayesPerf可将平均误差从传统线性缩放的40.1\%降至7.6\%，误差降低幅度达5.28倍，显著优于线性缩放与NeoMPX的单一事件建模思路。但BayesPerf同样存在不可忽视的局限：其一，其因子图建模仅聚焦于可通过显式公式描述的事件关联，未能充分纳入微架构层级的隐性交互效应——例如L1、L2、L3缓存间的数据驱逐机制（L1缓存的高频命中会减少L2缓存的访问请求，进而间接降低L3缓存的缺失率），这类跨层级、非公式化的关联关系未被纳入推理框架，成为潜在的误差来源；其二，贝叶斯推理过程涉及高维概率分布的积分与迭代优化，呈现极强的CPU计算密集性——纯软件实现下，单次HPC读取的 latency是原生 polling 方式的9倍，必须依赖FPGA定制化加速器（如基于Xilinx Virtex 7 FPGA的设计），通过高吞吐量随机数生成器与多EP引擎并行执行，才能将latency overhead控制在2\%以内，这无疑增加了技术落地的硬件成本与系统集成复杂度，限制了其在资源受限场景（如边缘计算节点）的应用。


从当前技术现状来看，PMCs多路复用的性能数据缩放算法已形成“工程化非线性调整”与“高精度关联推理”两大路径：NeoMPX以其相对简洁的非线性模型与低硬件依赖，适用于轻量级、实时性要求不极致的监测场景（如普通应用性能 profiling）；BayesPerf则以关联推理的高精度优势，面向深度性能分析场景（如数据中心级资源调度、微架构瓶颈定位）。但二者均未完全解决“精度-适应性-计算效率”的三角平衡问题：NeoMPX的固定非线性策略难以覆盖所有动态场景，BayesPerf虽提升了关联性建模能力，却因建模范围局限与计算复杂度，面临“隐性关联缺失”与“硬件加速依赖”的双重挑战。这些局限共同指向当前技术的核心瓶颈——如何在不显著增加计算开销的前提下，实现“显式关联+隐性交互”的全面建模，成为未来性能数据缩放算法突破的关键方向。

\section{超图分区算法研究现状}

超图分区作为处理高阶关系数据的重要基础技术，近年来在电子设计自动化、并行计算任务映射、复杂网络分析以及机器学习预处理等领域中得到广泛应用，其研究核心围绕如何在严格的负载平衡约束下最小化跨分区连接代价，并在可扩展性与划分质量之间取得稳健权衡。与传统图分割不同，超图以超边直接刻画多元实体间的群组相互作用，因此在目标函数设计、算法工程化以及并行化实现方面呈现出独特挑战与方法学演进。

当前主流方法以多级范式为支撑，其基本思想是在逐级缩减问题规模的过程中保留结构要义，并在最粗化层求解后通过逐层细化不断提升解的质量。具体而言，粗化阶段通过匹配与收缩策略将局部强关联顶点聚合为超级顶点，并对相应超边进行合并映射，以获得一条由原始超图到极小超图的层级链；关键在于匹配准则对结构信息的保真度影响显著，实际工程中常结合基于超边的关联度量、启发式的贪心选择以及确定性匹配以保证复现实验与并行执行的一致性。当规模降至可控阈值后，初始划分在最粗化层进行，既可以采用启发式的多路划分策略，也可以在小规模上结合谱方法或局部搜索以获得高质量起点。随后的细化阶段按层级逆向展开，将解映射回更细粒度的层级，同时利用超图版的FM类局部搜索对边界顶点进行移动增益评估与选择；为控制复杂度、提升可扩展性，工程实现中往往结合增益缓存与惰性更新以避免重复计算，并借助分区锁等并行控制策略在多核环境下实现近线性加速。该范式通过“简化—求解—还原”的闭环，有效降低了大规模实例的计算负担，同时保持划分质量的持续改进。

围绕多级范式的代表性实现之一是KaHyPar，其将多目标函数、灵活的粗化/细化策略以及高度参数化的控制接口整合为工业级可用的超图划分框架。在目标函数层面，除经典的超边切割代价外，KaHyPar支持基于连接度的代价建模以及多约束负载平衡，从而兼顾分区间通信量与分区内部负载均衡；在超图类型适配上，框架覆盖带权/无权与定向超图，并支持结构演化场景下的增量式处理。在工程实现上，KaHyPar对粗化与细化的并行化作了系统性优化：在粗化中采用线程安全的并行匹配，在细化中通过并行增益评估和局部同步避免热点，配合自适应的粗化比例与超边收缩策略，在稠密与稀疏实例上均衡质量与速度。大量公开基准测试显示，该框架在划分质量与运行效率上相较早期工具具有稳定优势，并在亿级规模数据上展现出良好的内存占用与可扩展特性。

近年来，围绕KaHyPar生态的研究进一步将多级范式拓展至动态、多目标与跨硬件加速等方向。一方面，面向结构随时间演化的动态超图，增量式多级流程通过保留历史匹配信息与引入局部化的增益更新，在保证质量的同时显著降低了重新粗化的代价，因而在在线工作负载或持续集成式设计场景中更具时效性。另一方面，多目标优化被纳入细化阶段的决策过程中，通过帕累托最优准则在切割代价、负载均衡与社群内聚度等指标间进行折中，使划分结果更契合下游任务的综合需求。此外，GPU加速版本通过对粗化与细化关键算子的并行重构，有效释放了大规模实例上的吞吐潜力；其与深度学习框架的联动也为超图神经网络等应用提供了高效的预处理通道。

跨领域应用同样验证了多级超图划分在真实复杂系统中的效能。在VLSI物理设计中，将电路模块划分为通信密度高的区域有助于降低跨区域连线与功耗；在量子电路切割问题中，以超图表达门与量子比特之间的高阶关联，能够在分解大规模电路时减少跨子电路通信的代价；在生物网络分析中，以蛋白质复合体为超边的建模形式有助于识别功能模块并提升下游表型关联的统计效力。这些案例表明，超图划分并非仅限于结构优化本身，而是作为上游结构化建模的一环，直接影响到后续计算的可分解性、通信局部性与统计稳健性。

尽管如此，当前研究仍面临数个值得重视的开放问题。首先，粗化阶段在“结构保真”与“规模缩减率”之间的张力依然突出：过度激进的收缩容易损伤高阶关系的语义，但过于保守又会削弱多级范式的复杂度红利。如何结合可学习的结构嵌入对匹配与收缩进行数据驱动的自适应调控，是提升粗化质量的潜在方向。其次，细化阶段的局部搜索虽已在增益缓存、惰性更新与并行执行方面取得进展，但在高度异构硬件与强非均匀数据分布场景下，如何构建更鲁棒的增益评估与多目标权衡机制仍待深入。再次，动态超图的增量式处理需要在质量、延迟与计算预算之间建立更细粒度的控制策略，避免在剧烈结构变动时出现质量震荡或计算开销失控。最后，从系统工程角度看，如何在保证可复现性与可调参性的同时，降低对硬件特性与平台依赖的敏感度，并与上层学习/推理工作流顺畅集成，仍是推动大规模落地的关键。

总体而言，以多级范式为核心的方法论已经为超图分区提供了坚实的理论与工程基础；KaHyPar及其扩展生态在目标函数建模、并行实现与跨场景适配方面不断推进，使得该领域在“质量—效率—可扩展性”的三元权衡上取得了兼顾。面向未来，结合表示学习指导的粗化策略、能够同时吸纳显式约束与隐式结构的细化推理，以及面向动态场景的低延迟增量式更新，将有望进一步提升划分的稳健性与场景泛化能力，并为包括VLSI设计、量子计算与生物网络在内的多学科应用提供更为强大的结构化支撑。
